package syf.huffmantree;

import java.util.*;
/**
 * 1、建立节点，存放数据（字符）和权重（出现的次数） 以及左右节点，
 * 2、得到字符串对应的数组
 * 3、构建赫夫曼树
 */
public class HuffmanCode {
    //用来存放赫夫曼表对应的 byte 和 路径码
    static Map<Byte,String> map=new HashMap<>();
    //拼接路径
    static StringBuilder pathString=new StringBuilder();
    public static void main(String[] args) {
        String s="i like like like java do you like a java";
        MyNode myNode = creatHuff(getList(s));
//        System.out.println(myNode);
//        myNode.preShow();
        Map<Byte, String> codes = getCodes(myNode);
//        System.out.println(codes);
        byte[]huff=zip(s.getBytes(),codes);
        System.out.println(Arrays.toString(huff));
    }
    //得到字符串对应的数组，排好序存进List中
    public static List<MyNode> getList(String s){
        //将字符串转化成数组
        byte[]bytes=s.getBytes();
//        System.out.println(bytes.length);
        //用来存放数据
        List<MyNode>list=new ArrayList<>();
        //用来计算，每个字符出现的次数
        Map<Byte,Integer> map=new HashMap<>();
        for (int i=0;i<s.length();i++){
            map.merge(bytes[i], 1, Integer::sum);
        }
        //将key和value取出并放进List集合中
        for (Map.Entry<Byte,Integer> m:map.entrySet()){
            list.add(new MyNode(m.getKey(),m.getValue()));
        }
        return list;
    }
    //构建哈夫曼树
    public static MyNode creatHuff(List<MyNode> list){
        while (list.size()>1){
            Collections.sort(list);
            MyNode leftNode = list.get(0);
            MyNode rightNode = list.get(1);
            MyNode parent=new MyNode(null,leftNode.weight+rightNode.weight);
            parent.left=leftNode;
            parent.right=rightNode;
            list.remove(leftNode);
            list.remove(rightNode);
            list.add(parent);
        }
        return list.get(0);
    }

    /**
     * 功能： 获取赫夫曼表
     * @param node 传入的根节点
     * @param code 左是0，右是1，判断0还是1
     * @param path 根路径
     */
    //生成赫夫曼表
    public static Map<Byte,String> getCodes(MyNode node,String code,StringBuilder path){
        //路径拼接
        StringBuilder builder = new StringBuilder(path);
        builder.append(code);
        if (node!=null){
            //非叶子节点
            if (node.data==null){
                getCodes(node.left,"0",builder);
                getCodes(node.right,"1",builder);
            }else {
                //叶子节点
                map.put(node.data,builder.toString());
            }
        }
        return map;
    }
    //重载
    public static Map<Byte,String> getCodes(MyNode node){
        return getCodes(node,"",pathString);
    }

    /**
     *
     * @param bytes 待发送信息转成的数组
     * @param map 包含每个字符对应的路径的map
     * @return 压缩后的数组
     */
    //将压缩后的赫夫曼表，返还成一个byte数组
    public static byte[] zip(byte[] bytes,Map<Byte,String> map){
        StringBuilder huffman=new StringBuilder();
        //将map中的2进制换出来
        for (byte x:bytes){
            huffman.append(map.get(x));
        }
        int count=huffman.length()/8;
        byte[] tmp;
        if (count==0)
            tmp=new byte[count];
        else {
            tmp=new byte[count+1];
        }
        int index=0;//记录字节的个数
        for (int i=0;i<huffman.length();i+=8){
            if (i+8<huffman.length()){
                tmp[index]= (byte) Integer.parseInt(huffman.substring(i,i+8),2);
            }else {
                tmp[index]= (byte) Integer.parseInt(huffman.substring(i),2);
            }
            index++;
        }
        return tmp;
    }
}
class MyNode implements Comparable<MyNode>{
    MyNode left;
    MyNode right;
    Byte data;
    int weight;
    public MyNode(Byte data, int weight) {
        this.data = data;
        this.weight = weight;
    }

    @Override
    public int compareTo(MyNode o) {
        //升序排列
        return this.weight-o.weight;
    }
    //前序遍历
    public void preShow(){
        System.out.println(this);
        if (this.left!=null)
            this.left.preShow();
        if (this.right!=null)
            this.right.preShow();
    }

    @Override
    public String toString() {
        return "MyNode{" +
                "data=" + data +
                ", weight=" + weight +
                '}';
    }
}